package com.example.leetcode.tree;

import com.example.leetcode.tree.common.TreeNode;
import com.example.leetcode.tree.common.TreePrinter;
import com.example.leetcode.tree.common.TreeUtils;

import java.util.ArrayList;
import java.util.List;

public class leetcode655 {
    public static void main(String[] args) {
        Integer[] root = {1};
        TreeNode tree = TreeUtils.generateLeetcodeTree(root);
        TreePrinter.printPrettyTree(tree);

        Solution solution = new Solution();
        List<List<String>> result = solution.printTree(tree);
        System.out.println(result);
    }


    static class Solution {
        private Integer maxHeight = 0;

        public List<List<String>> printTree(TreeNode root) {
            // 根节点高度是0
            dfs(root, 0);

            int m = maxHeight + 1;
            int n = (int) (Math.pow(2, maxHeight + 1) - 1);

            String[][] result = new String[m][n];

            for (int row = 0; row < m; row++) {
                for (int col = 0; col < n; col++) {
                    result[row][col] = "";
                }
            }

            dfs(root, result, 0, (n - 1) / 2);

            List<List<String>> res = new ArrayList<>();
            for (int row = 0; row < m; row++) {
                List<String> list = new ArrayList<>();
                for (int col = 0; col < n; col++) {
                    list.add(result[row][col]);
                }
                res.add(list);
            }
            return res;
        }

        public void dfs(TreeNode root, String[][] result, int row, int col) {
            if (root == null) {
                return;
            }
            result[row][col] = String.valueOf(root.val);
            if (root.left != null) {
                dfs(root.left, result, row + 1, (int) (col - Math.pow(2, maxHeight - row - 1)));
            }
            if (root.right != null) {
                dfs(root.right, result, row + 1, (int) (col + Math.pow(2, maxHeight - row - 1)));
            }
        }

        public void dfs(TreeNode root, Integer curHeight) {
            if (root == null) return;
            if (curHeight > maxHeight) {
                maxHeight = curHeight;
            }
            dfs(root.left, curHeight + 1);
            dfs(root.right, curHeight + 1);
        }
    }

}
